package leetcode.数学;

/**
 * Z 字形变换
 * <p>
 * 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
 * <p>
 * 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
 * <p>
 * L   C   I   R
 * E T O E S I I G
 * E   D   H   N
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
 * <p>
 * 请你实现这个将字符串进行指定行数变换的函数：
 * <p>
 * string convert(string s, int numRows);
 * 示例 1:
 * 输入: s = "LEETCODEISHIRING", numRows = 3
 * 输出: "LCIRETOESIIGEDHN"
 * <p>
 * 示例 2:
 * 输入: s = "LEETCODEISHIRING", numRows = 4
 * 输出: "LDREOEIIECIHNTSG"
 * 解释:
 * L     D     R
 * E   O E   I I
 * E C   I H   N
 * T     S     G
 * <p>
 * <p>
 * <p>
 * 找规律的题目：
 * <p>
 * 第一行、最后一行的时候会出现Z字的转折，
 * 我们发现第一行中 L 和 D 之间间隔 EETCO 个字符，也就是：
 * 这两行的每两个字母之间的间隔为: step = 2 * numRows - 2;
 * L 加6个位置后得到 D
 * <p>
 * 中间的行规律:
 * 如果是在 Z 字的上半部分, index = current + step;
 * <p>
 * 如果是在 Z 字的下半部分, index = current + step - 2 * row;
 * 也就是
 */
public class Test6Z字形变换 {

    public static String convert(String s, int numRows) {
        if (s.length() <= 2 || numRows == 1) {
            return s;
        }
        StringBuilder ans = new StringBuilder();
        // 1.处理第一行
        int step = 2 * numRows - 2;
        for (int i = 0; i < s.length(); i += step) {
            ans.append(s.charAt(i));
        }
        // 2. 处理中间行
        int row = 1;// 从矩阵的第二行开始，到道数第二行结束
        while (row < numRows - 1) {
            int index = row;
            while (index < s.length()) {// 索引不得越界，然后遍历整个 s，把符合规律的加入
                ans.append(s.charAt(index));
                int nextIndex = index + step - 2 * row;
                if (nextIndex < s.length()) {
                    ans.append(s.charAt(nextIndex));
                }
                index += step;
            }
            row++;
        }
        // 3. 处理最后一行
        for (int i = numRows - 1; i < s.length(); i += step) {
            ans.append(s.charAt(i));
        }
        return ans.toString();
    }

    public static void main(String[] args) {
//        System.out.println(convert2("LEETCODEISHIRING", 4));
//        System.out.println(convert2("PAYPALISHIRING", 3));
        System.out.println(convert2("abcdef", 5));
    }


    public static String convert2(String s, int numRows) {
        if (s.length() <= 2 || numRows == 1) {
            return s;
        }
        StringBuilder ans = new StringBuilder();
        // 1.处理第一行
        int step = 2 * numRows - 2;
        for (int i = 0; i < s.length(); i += step) {
            ans.append(s.charAt(i));
        }
        // 2. 处理中间行
        // 先计算中间行的差值
        int big = step - 2;
        int small = big - 2;
        if (small <= 0)
            small = big;
        int index = 1;
        while (index < numRows - 1) {
            int rol = index;
            boolean turn = false;
            for (; index < s.length(); ) {
                ans.append(s.charAt(index));
                if ((rol & 1) == 1) {
                    if (!turn) {
                        index += big;
                        turn = true;
                    } else {
                        index += small;
                        turn = false;
                    }
                } else {
                    if (!turn) {
                        index += small;
                        turn = true;
                    } else {
                        index += big;
                        turn = false;
                    }
                }
            }
            turn = false;
            index = rol;
            index++;
        }
        // 3. 处理最后一行
        for (int i = numRows - 1; i < s.length(); i += step) {
            ans.append(s.charAt(i));
        }
        return ans.toString();
    }
}
